<html>
<head><meta charset="utf-8"><title>flat-merge iterators · general · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/index.html">general</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/flat-merge.20iterators.html">flat-merge iterators</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="222241444"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/flat-merge%20iterators/near/222241444" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> akraines <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/flat-merge.20iterators.html#222241444">(Jan 10 2021 at 20:51)</a>:</h4>
<p>First of all, thanks for all your help. I just realised that I wasn't in the "help" section, but the <em>compiler</em> help section. I'm moving it over to general so as not to spam you.<br>
I tried it out. I think lat <span class="user-mention" data-user-id="216206">@lcnr</span> is correct that this isn't a bottleneck of the algorithm, however I would still like to know how to get this to work. The issue is now that the borrow-checker wants me to make the inner closure move, but then I cannot keep track of the group count to correctly number my combinations.</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="k">pub</span><span class="w"> </span><span class="k">fn</span> <span class="nf">get_combinations</span><span class="p">(</span><span class="n">all_values</span>: <span class="kp">&amp;</span><span class="nc">ValueSet</span><span class="p">)</span><span class="w"> </span>-&gt; <span class="nc">BTreeMap</span><span class="o">&lt;</span><span class="n">Value</span><span class="p">,</span><span class="w"> </span><span class="nb">Vec</span><span class="o">&lt;</span><span class="n">Combination</span><span class="o">&gt;&gt;</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">simple_values</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="o">&amp;</span><span class="n">all_values</span><span class="p">.</span><span class="n">simple</span><span class="p">;</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">comb_max</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">(</span><span class="mi">2_</span><span class="k">usize</span><span class="p">.</span><span class="n">pow</span><span class="p">((</span><span class="n">simple_values</span><span class="p">.</span><span class="n">len</span><span class="p">())</span><span class="w"> </span><span class="k">as</span><span class="w"> </span><span class="kt">u32</span><span class="p">));</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">values</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nb">Box</span>::<span class="n">new</span><span class="p">((</span><span class="mi">1</span><span class="o">..</span><span class="n">comb_max</span><span class="p">).</span><span class="n">map</span><span class="p">(</span><span class="o">|</span><span class="n">v</span><span class="o">|</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="kd">let</span><span class="w"> </span><span class="n">value</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">get_combination_value</span><span class="p">(</span><span class="o">&amp;</span><span class="n">v</span><span class="p">,</span><span class="w"> </span><span class="n">all_values</span><span class="p">);</span><span class="w"></span>
<span class="w">        </span><span class="n">Combination</span><span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="n">value</span><span class="p">,</span><span class="w"> </span><span class="n">combination</span>: <span class="nc">v</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}))</span><span class="w"> </span><span class="k">as</span><span class="w"> </span><span class="nb">Box</span><span class="o">&lt;</span><span class="k">dyn</span><span class="w"> </span><span class="nb">Iterator</span><span class="o">&lt;</span><span class="n">Item</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Combination</span><span class="o">&gt;&gt;</span><span class="p">;</span><span class="w"></span>

<span class="w">    </span><span class="k">if</span><span class="w"> </span><span class="kd">let</span><span class="w"> </span><span class="nb">Some</span><span class="p">(</span><span class="n">grouped_values</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="o">&amp;</span><span class="n">all_values</span><span class="p">.</span><span class="n">complex</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">prevcount</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">simple_values</span><span class="p">.</span><span class="n">len</span><span class="p">();</span><span class="w"></span>
<span class="w">        </span><span class="k">for</span><span class="w"> </span><span class="n">cur_group</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">grouped_values</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="kd">let</span><span class="w"> </span><span class="n">count</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">prevcount</span><span class="p">;</span><span class="w"></span>
<span class="w">            </span><span class="n">prevcount</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="n">grouped_values</span><span class="p">.</span><span class="n">len</span><span class="p">();</span><span class="w"></span>
<span class="w">            </span><span class="n">values</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nb">Box</span>::<span class="n">new</span><span class="p">(</span><span class="n">values</span><span class="p">.</span><span class="n">flat_map</span><span class="p">(</span><span class="k">move</span><span class="w"> </span><span class="o">|</span><span class="n">prev_c</span><span class="o">|</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                </span><span class="n">cur_group</span><span class="p">.</span><span class="n">iter</span><span class="p">().</span><span class="n">enumerate</span><span class="p">().</span><span class="n">map</span><span class="p">(</span><span class="o">|</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">v</span><span class="p">)</span><span class="o">|</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                    </span><span class="n">Combination</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                        </span><span class="n">value</span>: <span class="nc">prev_c</span><span class="p">.</span><span class="n">value</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">v</span><span class="p">,</span><span class="w"></span>
<span class="w">                        </span><span class="n">combination</span>: <span class="nc">prev_c</span><span class="p">.</span><span class="n">combination</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="p">(</span><span class="mi">1</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="p">(</span><span class="n">count</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">i</span><span class="p">)),</span><span class="w"></span>
<span class="w">                    </span><span class="p">}</span><span class="w"></span>
<span class="w">                </span><span class="p">})</span><span class="w"></span>
<span class="w">            </span><span class="p">}));</span><span class="w"></span>
<span class="w">        </span><span class="p">};</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>

<span class="w">    </span><span class="n">values</span><span class="p">.</span><span class="n">fold</span><span class="p">(</span><span class="n">BTreeMap</span>::<span class="n">new</span><span class="p">(),</span><span class="w"> </span><span class="o">|</span><span class="k">mut</span><span class="w"> </span><span class="n">acc</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="o">|</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="n">acc</span><span class="p">.</span><span class="n">entry</span><span class="p">(</span><span class="n">c</span><span class="p">.</span><span class="n">value</span><span class="p">).</span><span class="n">or_insert</span><span class="p">(</span><span class="nb">Vec</span>::<span class="n">new</span><span class="p">()).</span><span class="n">push</span><span class="p">(</span><span class="n">c</span><span class="p">);</span><span class="w"></span>
<span class="w">        </span><span class="n">acc</span><span class="w"></span>
<span class="w">    </span><span class="p">})</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>
<p>And the error is:</p>
<div class="codehilite"><pre><span></span><code>error: captured variable cannot escape `FnMut` closure body
  --&gt; src/Comparer.rs:90:17
   |
87 |               let count = prevcount;
   |                   ----- variable defined here
88 |               prevcount += grouped_values.len();
89 |               values = Box::new(values.flat_map(move |prev_c:Combination| {
   |                                                                         - inferred to be a `FnMut` closure
90 | /                 cur_group.iter().enumerate().map(|(i, v)| {
91 | |                     Combination {
92 | |                         value: prev_c.value + v,
93 | |                         combination: prev_c.combination + (1 &lt;&lt; (count + i)),
   | |                                                                  ----- variable captured here
94 | |                     }
95 | |                 })
   | |__________________^ returns a reference to a captured variable which escapes the closure body
   |
   = note: `FnMut` closures only have access to their captured variables while they are executing...
   = note: ...therefore, they cannot allow references to captured variables to escape
</code></pre></div>



<a name="222241681"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/flat-merge%20iterators/near/222241681" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> akraines <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/flat-merge.20iterators.html#222241681">(Jan 10 2021 at 20:57)</a>:</h4>
<p>Is there a different way for me to make values consume the previous version of itself and create a new iterator of the result.<br>
Before trying this out, I simply made values into a Vec, and created a new Vec for each iteration of the grouped_values (pre-allocating the vec, since the capacity is predictable),  and made values = new_values.</p>



<a name="222242124"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/flat-merge%20iterators/near/222242124" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> akraines <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/flat-merge.20iterators.html#222242124">(Jan 10 2021 at 21:07)</a>:</h4>
<p>This is the working version using vec's - I think that it is good enough, but I want to know if it is possible to do the same without creating intermediary storage - b/c in theory, this algorithm only needs to iterate over all the values once.</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="k">pub</span><span class="w"> </span><span class="k">fn</span> <span class="nf">get_combinations</span><span class="p">(</span><span class="n">all_values</span>: <span class="kp">&amp;</span><span class="nc">ValueSet</span><span class="p">)</span><span class="w"> </span>-&gt; <span class="nc">BTreeMap</span><span class="o">&lt;</span><span class="n">Value</span><span class="p">,</span><span class="w"> </span><span class="nb">Vec</span><span class="o">&lt;</span><span class="n">Combination</span><span class="o">&gt;&gt;</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">simple_values</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="o">&amp;</span><span class="n">all_values</span><span class="p">.</span><span class="n">simple</span><span class="p">;</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">comb_max</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">(</span><span class="mi">2_</span><span class="k">usize</span><span class="p">.</span><span class="n">pow</span><span class="p">((</span><span class="n">simple_values</span><span class="p">.</span><span class="n">len</span><span class="p">())</span><span class="w"> </span><span class="k">as</span><span class="w"> </span><span class="kt">u32</span><span class="p">));</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">values</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">(</span><span class="mi">1</span><span class="o">..</span><span class="n">comb_max</span><span class="p">).</span><span class="n">map</span><span class="p">(</span><span class="o">|</span><span class="n">v</span><span class="o">|</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="kd">let</span><span class="w"> </span><span class="n">value</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">get_combination_value</span><span class="p">(</span><span class="o">&amp;</span><span class="n">v</span><span class="p">,</span><span class="w"> </span><span class="n">all_values</span><span class="p">);</span><span class="w"></span>
<span class="w">        </span><span class="n">Combination</span><span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="n">value</span><span class="p">,</span><span class="w"> </span><span class="n">combination</span>: <span class="nc">v</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}).</span><span class="n">collect</span>::<span class="o">&lt;</span><span class="nb">Vec</span><span class="o">&lt;</span><span class="n">Combination</span><span class="o">&gt;&gt;</span><span class="p">();</span><span class="w"></span>

<span class="w">    </span><span class="k">if</span><span class="w"> </span><span class="kd">let</span><span class="w"> </span><span class="nb">Some</span><span class="p">(</span><span class="n">grouped_values</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="o">&amp;</span><span class="n">all_values</span><span class="p">.</span><span class="n">complex</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">count</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">simple_values</span><span class="p">.</span><span class="n">len</span><span class="p">();</span><span class="w"></span>
<span class="w">        </span><span class="k">for</span><span class="w"> </span><span class="n">cur_group</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">grouped_values</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">new_values</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nb">Vec</span>::<span class="n">with_capacity</span><span class="p">(</span><span class="n">count</span><span class="w"> </span><span class="o">*</span><span class="w"> </span><span class="n">cur_group</span><span class="p">.</span><span class="n">len</span><span class="p">());</span><span class="w"></span>
<span class="w">            </span><span class="k">for</span><span class="w"> </span><span class="n">prev_c</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="o">&amp;</span><span class="n">values</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">v</span><span class="p">)</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">cur_group</span><span class="p">.</span><span class="n">iter</span><span class="p">().</span><span class="n">enumerate</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                    </span><span class="n">new_values</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">Combination</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                        </span><span class="n">value</span>: <span class="nc">prev_c</span><span class="p">.</span><span class="n">value</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">v</span><span class="p">,</span><span class="w"></span>
<span class="w">                        </span><span class="n">combination</span>: <span class="nc">prev_c</span><span class="p">.</span><span class="n">combination</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="p">(</span><span class="mi">1</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="p">(</span><span class="n">count</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">i</span><span class="p">)),</span><span class="w"></span>
<span class="w">                    </span><span class="p">});</span><span class="w"></span>
<span class="w">                </span><span class="p">}</span><span class="w"></span>
<span class="w">                </span><span class="n">new_values</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="o">*</span><span class="n">prev_c</span><span class="p">);</span><span class="w"></span>
<span class="w">            </span><span class="p">}</span><span class="w"></span>
<span class="w">            </span><span class="n">count</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="n">cur_group</span><span class="p">.</span><span class="n">len</span><span class="p">();</span><span class="w"></span>
<span class="w">            </span><span class="n">values</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">new_values</span><span class="p">;</span><span class="w"></span>
<span class="w">        </span><span class="p">};</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>

<span class="w">    </span><span class="n">values</span><span class="p">.</span><span class="n">iter</span><span class="p">().</span><span class="n">fold</span><span class="p">(</span><span class="n">BTreeMap</span>::<span class="n">new</span><span class="p">(),</span><span class="w"> </span><span class="o">|</span><span class="k">mut</span><span class="w"> </span><span class="n">acc</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="o">|</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="n">acc</span><span class="p">.</span><span class="n">entry</span><span class="p">(</span><span class="n">c</span><span class="p">.</span><span class="n">value</span><span class="p">).</span><span class="n">or_insert</span><span class="p">(</span><span class="nb">Vec</span>::<span class="n">new</span><span class="p">()).</span><span class="n">push</span><span class="p">(</span><span class="o">*</span><span class="n">c</span><span class="p">);</span><span class="w"></span>
<span class="w">        </span><span class="n">acc</span><span class="w"></span>
<span class="w">    </span><span class="p">})</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>